|
In number theory, the Schröder–Hipparchus numbers form an integer sequence that can be used to count the number of plane trees with a given set of leaves, the number of ways of inserting parentheses into a sequence, and the number of ways of dissecting a convex polygon into smaller polygons by inserting diagonals. These numbers begin :1, 1, 3, 11, 45, 197, 903, 4279, 20793, 103049, ... . They are also called the super-Catalan numbers, the little Schröder numbers, or the Hipparchus numbers, after Eugène Charles Catalan and his Catalan numbers, Ernst Schröder and the closely related Schröder numbers, and the ancient Greek mathematician Hipparchus who appears from evidence in Plutarch to have known of these numbers. ==Combinatorial enumeration applications== The Schröder–Hipparchus numbers may be used to count several closely related combinatorial objects:〔〔.〕〔.〕〔.〕 *The ''n''th number in the sequence counts the number of different ways of subdividing of a polygon with ''n'' + 1 sides into smaller polygons by adding diagonals of the original polygon. *The ''n''th number counts the number of different plane trees with ''n'' leaves and with all internal vertices having two or more children. *The ''n''th number counts the number of different ways of inserting parentheses into a sequence of ''n'' symbols, with each pair of parentheses surrounding two or more symbols or parenthesized groups, and without any parentheses surrounding the entire sequence. *The ''n''th number counts the number of faces of all dimensions of an associahedron ''K''''n'' + 1 of dimension ''n'' − 1, including the associahedron itself as a face, but not including the empty set. For instance, the two-dimensional associahedron ''K''4 is a pentagon; it has five vertices, five faces, and one whole associahedron, for a total of 11 faces. As the figure shows, there is a simple combinatorial equivalence between these objects: a polygon subdivision has a plane tree as a form of its dual graph, the leaves of the tree correspond to the symbols in a parenthesized sequence, and the internal nodes of the tree other than the root correspond to parenthesized groups. The parenthesized sequence itself may be written around the perimeter of the polygon with its symbols on the sides of the polygon and with parentheses at the endpoints of the selected diagonals. This equivalence provides a bijective proof that all of these kinds of objects are counted by a single integer sequence.〔 The same numbers also count the number of double permutations (sequences of the numbers from 1 to ''n'', each number appearing twice, with the first occurrences of each number in sorted order) that avoid the permutation patterns 12312 and 121323.〔.〕 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Schröder–Hipparchus number」の詳細全文を読む スポンサード リンク
|